package 动态规划;

import org.junit.Test;

public class Solution221最大正方形 {
    /**
     * dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows+1][cols+1];
        int maxLength=0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if(matrix[i-1][j-1]=='1'){
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    maxLength=Math.max(maxLength, dp[i][j]);
                }
            }
        }
        return maxLength*maxLength;
    }

    @Test
    public void test(){
        char[][] arr=new char[1][0];
        maximalSquare(arr);
    }
}
